Insert new interval (merge if necessary)

Time: O(N); Space: O(1); hard

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals: [1, 3], [6, 9]; newInterval: [2, 5]

Output: [[1, 5], [6, 9]]

Example 2:

Input: intervals: [1, 2], [3, 5], [6, 7], [8, 10], [12, 16]; newInterval: [4, 9]

Output: [[1, 2], [3, 10], [12, 16]]

Explanation:

  • This is because the newInterval [4, 9] overlaps with [3, 5], [6, 7], [8, 10].

[9]:

# Definition for an interval.
class Interval:
    def __init__(self, start = 0, end = 0):
        self.start = start
        self.end = end

    def __repr__(self):
        return "[{}, {}]".format(self.start, self.end)

class Solution1(object):
    def insert(self, intervals, newInterval) -> list:
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        result = []
        i = 0
        while i < len(intervals) and newInterval.start > intervals[i].end:
            result += intervals[i],
            i += 1

        while i < len(intervals) and newInterval.end >= intervals[i].start:
            newInterval = Interval(min(newInterval.start, intervals[i].start), \
                                   max(newInterval.end, intervals[i].end))
            i += 1

        result += newInterval,         # add set -> comma
        result += intervals[i:]

        return result

[11]:

s = Solution1()
intervals = [Interval(1, 3), Interval(6, 9)]
newInterval = Interval(2, 5)
list_of_intervals = s.insert(intervals, newInterval)
res = []
for ivl in list_of_intervals:
    res.append([ivl.start, ivl.end])
assert res == [[1, 5], [6, 9]]

intervals = [Interval(1, 2), Interval(3, 5), Interval(6, 7), Interval(8, 10), Interval(12, 16)]
newInterval = Interval(4, 9)
list_of_intervals = s.insert(intervals, newInterval)
res = []
for ivl in list_of_intervals:
    res.append([ivl.start, ivl.end])
assert res == [[1, 2], [3, 10], [12, 16]]